/*
 * @lc app=leetcode.cn id=24 lang=swift
 *
 * [24] 两两交换链表中的节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution24 {
    // 递归法
    func swapPairs(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        let newHead = head?.next
        head?.next = swapPairs(newHead?.next)
        newHead?.next = head
        return newHead
    }
    // 两两交换链表中的节点
    // 采用递归或者迭代法
    func swapPairs2(_ head: ListNode?) -> ListNode? {
        let vHead = ListNode(-1)
        vHead.next = head
        var pre: ListNode? = vHead
        var p1: ListNode? = vHead.next
        var p2: ListNode? = vHead.next?.next
        while p1 != nil && p2 != nil {
            let next = p2?.next
            pre?.next = p2
            p2?.next = p1
            p1?.next = next
            
            pre = p1
            
            p1 = p1?.next
            p2 = p1?.next
        }
        return vHead.next
    }
    
    static func test()  {
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        let node3 = ListNode(3)
        let node4 = ListNode(4)
        node1.next = node2
        node2.next = node3
        node3.next = node4
        
        let solution = Solution24()
        let result = solution.swapPairs2(node1)
        
        print(result)
    }
}
// @lc code=end

